/*
 * bwtBiyectivo.cpp
 */

#include <cstdlib>  // qsort();
#include <cstring>  // memcpy();
#include "./bwtBiyectivo.h"

#define RANGO 256

extern unsigned char bloque[];  // Necesario que sea global porque lo usa la funcion de comparación del qsort().
extern unsigned int ciclos[];  // Necesario que sea global porque lo usa la funcion de comparación del qsort().

void lyndonizar(unsigned char bloque[], unsigned char ultimaColumna[], unsigned int ciclos[], const unsigned int posicionFin);
void buscarRepetidos(unsigned char bloque[], unsigned int ciclos[], const unsigned int posicionFin);
bool hayOtraSubcadenaMenor(unsigned char bloque[], unsigned int ciclos[], const unsigned int inicioSubcadActual, const unsigned int inicioSubcadAProbar);
void cerrarCiclo(unsigned char bloque[], unsigned int ciclos[], const int posicionInicio, const int posicionFin);
int compararSubcadenas(const unsigned int *pInicioSubcad1, const unsigned int *pInicioSubcad2);
int comparar(const unsigned int *pInicio, const unsigned int *pFin);

void bwtBiyectivo_codificar(unsigned char bloque[], unsigned int cadenaLargo) {
	unsigned char ultimaColumna[cadenaLargo];
	unsigned int indices[cadenaLargo];
	unsigned int contador;

	// Cargo los indices con el valor de su posicion en el vector.
	for (contador = 0; contador < cadenaLargo; ++contador) {
		indices[contador] = contador;
	}

	// Cargo el vector "ultimaColumna" como la cadena original rotada una posicion a la derecha.
	unsigned int posicionFin = cadenaLargo - 1;
	for (contador = 0; contador < posicionFin; ++contador) {
		ultimaColumna[contador + 1] = bloque[contador];
	}
	ultimaColumna[0] = bloque[cadenaLargo - 1];

	lyndonizar(bloque, ultimaColumna, ciclos, posicionFin);

	{
		::qsort(indices, cadenaLargo, sizeof(unsigned int), (int (*)(const void *, const void *)) compararSubcadenas);}
		//::qsort(indices, cadenaLargo, sizeof(unsigned int), (int (*)(const void *, const void *)) comparar);}

		// Cargo en el bloque la cadena transformada.
	for (contador = 0; contador < cadenaLargo; ++contador) {
		bloque[contador] = ultimaColumna[indices[contador]];
	}
}

void bwtBiyectivo_decodificar(unsigned char bloque[], unsigned int cadenaLargo) {
	unsigned int cantidades[RANGO];
	unsigned int charsAcumulados[RANGO];
	unsigned char ciclos[cadenaLargo];
	unsigned int T[cadenaLargo];
	unsigned char auxiliar[cadenaLargo];
	enum tipoDeCaracter {
		SIN_PROCESAR = 3, PRIMERO_DE_CICLO = 4, COLA_DE_CICLO = 5
	};
	unsigned int contador;
	// Inicializo el vector "cantidades" con ceros.
	for (contador = 0; contador < RANGO; ++contador) {
		cantidades[contador] = 0;
	}

	// Cargo el vector "ciclos" con 'SIN_PROCESAR' hasta la longitud del bloque.
	// Cargo el vector "cantidades" con la cantidad de ocurrencias de cada caracter en el bloque.
	for (contador = 0; contador < cadenaLargo; ++contador) {
		ciclos[contador] = SIN_PROCESAR;  // Marco el ciclo como 'SIN_PROCESAR'.
		++cantidades[bloque[contador]];  // Incremento en uno la cantidad de ocurrencias de ese caracter.
	}

	// Cargo en el vector "charsAcumulados" la cantidad de caracteres menores al caracter procesado que hay en el bloque.
	unsigned int acumulador = 0;
	for (contador = 0; contador < RANGO; ++contador) {
		charsAcumulados[contador] = acumulador;  // Asigno la cantidad de caracteres menores al caracter procesado que hay en el bloque a la posición correspondiente del vector "charsAcumulados".
		acumulador += cantidades[contador];  // Incremento el acumulador.
		cantidades[contador] = 0;  // Cargo con cero la posición correspondiente al caracter procesado en el vector "cantidades" para poder usarlo como contador de la cantidad de caracteres procesados al ir armando el vector de permutaciones "T".
	}

	unsigned char caracter;
	for (contador = 0; contador < cadenaLargo; ++contador) {
		caracter = bloque[contador];  // El caracter que voy a procesar.
		T[cantidades[caracter] + charsAcumulados[caracter]] = contador;  // Cargo en la posición del vector "T" equivalente a la cantidad de caracteres que hay en el bloque y que son menores al actual, más la cantidad de caracteres iguales al actual que ya fueron procesados, el valor del contador.
		++cantidades[caracter];  // Cuento esta ocurrencia de este caracter.
	}

	bool todaviaFalta = true;
	contador = 0;
	unsigned int contador2, contador3 = 0;
	do {
		ciclos[contador] = PRIMERO_DE_CICLO;  // Lo marco como 'PRIMERO_DE_CICLO'.
		contador2 = 0;  // Inicializo el contador de posiciones del bloque.
		contador = T[contador];  // Cargo la proxima posición del bloque.
		// Mientras no vuelva a la posición inicial del ciclo actual y no me pase del fin del bloque.
		while ((ciclos[contador] != PRIMERO_DE_CICLO) && (contador2 < cadenaLargo)) {  // Se puede quitar "(contador2 < cadenaLargo)".
			ciclos[contador] = COLA_DE_CICLO;  // Marco la posición como parte de un ciclo.
			contador = T[contador];  // Cargo la posición del siguiente caracter.
			++contador2;  // Se puede quitar.
		}
		contador2 = contador;  // Cargo la posición de comienzo del ciclo actual.
		// Mientras no me pase del fin del bloque y no encuentre una posición que no forma parte aún de un ciclo.
		while ((contador2 < cadenaLargo) && (ciclos[contador2] != SIN_PROCESAR)) {
			++contador2;  // Incremento la posición.
		}
		// Si la posición forma parte de un ciclo o llegué al final del bloque.
		if ((ciclos[contador2] != SIN_PROCESAR) || (contador2 == cadenaLargo)) {
			todaviaFalta = false;  // Ya no necesito seguir iterando.
		} else {
			contador = contador2;  // Cargo la posición del nuevo inicio de ciclo.
		}
	} while (todaviaFalta);

	int contador4 = cadenaLargo - 1;  // Inicializo el contador de posiciones para recorrer el vector de ciclos de atrás para adelante.
	while (contador4 >= 0) {  // Mientras no me pase del comienzo del bloque.
		if (ciclos[contador4] == PRIMERO_DE_CICLO) {  // Si encuentro un comienzo de ciclo.
			todaviaFalta = true;
			contador2 = T[contador4];  // Cargo la próxima posición del ciclo.
			while (todaviaFalta) {
				if (contador4 == contador2) {  // Si volví al comienzo del ciclo.
					todaviaFalta = false;  // Ya terminé de procesar este ciclo.
				} else {  // Si no estoy en el comienzo del ciclo.
					auxiliar[contador3++] = bloque[contador2];  // Emito el caracter correspondiente.
					contador2 = T[contador2];  // Cargo la próxima posición del ciclo.
				}
			}
			auxiliar[contador3++] = bloque[contador2];  // Emito el último caracter.
		}
		--contador4;  // Sigo buscando un nuevo comienzo de ciclo en una posición anterior del vector de ciclos.
	}
	memcpy(bloque, auxiliar, sizeof(auxiliar));  // Copio los caracteres emitidos al bloque.
}

void lyndonizar(unsigned char bloque[], unsigned char ultimaColumna[], unsigned int ciclos[], const unsigned int posicionFin) {
	unsigned int posicionFinAux = posicionFin;  // Almaceno la posición de la cadena hasta donde puedo buscar una Lyndon word.
	unsigned int posicionInicioAux;
	buscarRepetidos(bloque, ciclos, posicionFinAux);  // Busco sub-cadenas de caracteres repetidos en la cadena.
	bool todaviaFalta = true;
	while (todaviaFalta) {
		if (posicionFinAux == 0) {  // Si solo queda el primer caracter.
			ciclos[0] = 0;  // Lo marco como un ciclo en sí mismo.
			todaviaFalta = false;
		} else {
			ciclos[posicionFinAux] = 0;
			posicionInicioAux = posicionFinAux;  // La primer sub-cadena que puedo suponer es la de un solo caracter.
			// Ciclo por todas las posibles cadenas mínimas (el vector ciclos tiene secuencias de posiciones que me mandan al siguiente caracter no repetido en la cadena original).
			for (unsigned int contador = 0; contador < posicionFinAux; contador = ciclos[contador]) {
				if (hayOtraSubcadenaMenor(bloque, ciclos, posicionInicioAux, contador)) {  // Si la sub-cadena que empieza en la posición "posicionInicioAux" no es la menor que puedo tomar.
					posicionInicioAux = contador;  // Tomo la sub-cadena que empieza en la posición "contador".
				}
			}
			cerrarCiclo(bloque, ciclos, posicionInicioAux, posicionFinAux);  // Llamo a cerrarCiclo() con las posiciones de inicio y fin de la cadena encontrada.
			ultimaColumna[posicionInicioAux] = bloque[posicionFinAux];  // Cargo en la posición del primer caracter de la sub-cadena en el vector "ultimaColumna", el último caracter de la sub-cadena.
			if (posicionInicioAux == 0) {  // Si la sub-cadena procesada era la primera del bloque.
				todaviaFalta = false;  // Ya procesé el bloque completo, así que no necesito seguir procesando.
			} else {
				posicionFinAux = posicionInicioAux - 1;  // La posición del último caracter de la siguiente sub-cadena a procesar será la posición anterior a la del primer caracter de la sub-cadena que acabamos de procesar.
				ultimaColumna[0] = bloque[posicionFinAux];  // Cargo en la primer posición del vector "ultimaColumna", el último caracter de la sub-cadena más larga que podría tomar en el siguiente paso.
			}
		}
	}
	return;
}

// Busca cadenas de caracteres repetidos en el bloque.
void buscarRepetidos(unsigned char bloque[], unsigned int ciclos[], const unsigned int posicionFin) {
	unsigned char caracterAnterior = bloque[posicionFin];  // Almaceno el último caracter de la cadena.
	unsigned int posicionCaracterDistinto = posicionFin;  // Almaceno la posición del último caracter de la cadena.
	// Recorro la cadena de derecha a izquierda (un ciclo por cada caracter).
	for (int posicionActual = posicionFin; posicionActual >= 0; --posicionActual) {
		if (bloque[posicionActual] != caracterAnterior) {  // Si el caracter de esta posición es distinto al anterior.
			caracterAnterior = bloque[posicionActual];  // Almaceno el nuevo caracter.
			posicionCaracterDistinto = posicionActual + 1;  // Guardo la posición donde he visto el caracter anterior por última vez en la cadena.
		}
		ciclos[posicionActual] = posicionCaracterDistinto;  // Almaceno en la posición actual del vector de ciclos, la posición de la primera ocurrencia de un caracter distinto al actual en la cadena (comparando desde la posición actual).
	}
	ciclos[posicionFin] = 0;  // El ciclo se cierra haciendo apuntar la última posición del vector de ciclos a la primera posición de la cadena.
	return;
}

// Determina si existe otra subcadena menor que la que comienza en "inicioSubcadActual" (probando con cadenas que comiencen en "inicioSubcadAProbar" o más adelante.
bool hayOtraSubcadenaMenor(unsigned char bloque[], unsigned int ciclos[], const unsigned int inicioSubcadActual, const unsigned int inicioSubcadAProbar) {
	if (bloque[inicioSubcadActual] != bloque[inicioSubcadAProbar]) {  // Si los primeros caracteres de ambas sub-cadenas no son iguales.
		if (bloque[inicioSubcadActual] < bloque[inicioSubcadAProbar]) {  // Si el primer caracter de la sub-cadena actual es menor que el primer caracter de la sub-cadena que estoy probando.
			return false;  // No hay otra sub-cadena menor empezando en la posición "inicioSubcadAProbar".
		} else {
			return true;  // Sí hay otra sub-cadena menor empezando en la posición "inicioSubcadAProbar".
		}
	} else {  //  Los primeros caracteres de ambas sub-cadenas son iguales.
		unsigned int posSubcadActual = inicioSubcadActual;  // Hago una copia para poder ir recoriendo la sub-cadena.
		unsigned int posSubcadAProbar = inicioSubcadAProbar;  // Hago una copia para poder ir recoriendo la sub-cadena.
		bool todaviaFalta = true;
		bool diLaVueltaEnCadenaAProbar = false, diLaVueltaEnCadenaActual = false;
		do {
			if (posSubcadActual < ciclos[posSubcadActual]) {  // Si el caracter actual de la sub-cadena actual no es el último de la sub-cadena buscada.
				if (posSubcadAProbar < ciclos[posSubcadAProbar]) {  // Si el caracter actual de la sub-cadena a probar no es el último de la sub-cadena buscada.
					unsigned int cantOcurrSubcadActual = ciclos[posSubcadActual] - posSubcadActual;  // Cantidad de ocurrencias ininterrumpidas (repeticiones + 1) del caracter actual en la sub-cadena actual a partir de la posición actual en la subcadena actual.
					unsigned int cantOcurrSubcadAProbar = ciclos[posSubcadAProbar] - posSubcadAProbar;  // Cantidad de ocurrencias ininterrumpidas (repeticiones + 1) del caracter actual en la sub-cadena a probar a partir de la posición actual en la subcadena a probar.
					if (cantOcurrSubcadActual == cantOcurrSubcadAProbar) {  // Si la cantidad de ocurrencias ininterrumpidas (repeticiones + 1) del caracter actual (a partir de las posiciones actuales respectivas) es igual en ambas sub-cadenas.
						posSubcadActual = ciclos[posSubcadActual];  // Salto en la sub-cadena actual al siguiente caracter distinto.
						posSubcadAProbar = ciclos[posSubcadAProbar];  // Salto en la sub-cadena a probar al siguiente caracter distinto.
					} else {  // La cantidad de ocurrencias ininterrumpidas (repeticiones + 1) del caracter actual (a partir de las posiciones actuales respectivas) no es igual en ambas sub-cadenas.
						if (cantOcurrSubcadActual > cantOcurrSubcadAProbar) {  // Si la cantidad de ocurrencias ininterrumpidas (repeticiones + 1) del caracter actual (a partir de las posiciones actuales respectivas) es mayor en la sub-cadena actual.
							// Salto en ambas sub-cadenas tantas posiciones como ocurrencias ininterrumpidas (repeticiones + 1) del caracter actual (a partir de la posición actual en la sub-cadena a probar) hay en la sub-cadena a probar.
							posSubcadActual += ciclos[posSubcadAProbar] - posSubcadAProbar;  // Salto en la sub-cadena actual tantas posiciones como ocurrencias ininterrumpidas (repeticiones + 1) del caracter actual (a partir de la posición actual en la sub-cadena a probar) hay en la sub-cadena a probar.
							posSubcadAProbar = ciclos[posSubcadAProbar];  // Salto en la sub-cadena a probar al siguiente caracter distinto.
						} else {  // La cantidad de ocurrencias ininterrumpidas (repeticiones + 1) del caracter actual (a partir de las posiciones actuales respectivas) es menor en la sub-cadena actual.
							// Salto en ambas sub-cadenas tantas posiciones como ocurrencias ininterrumpidas (repeticiones + 1) del caracter actual (a partir de la posición actual en la sub-cadena actual) hay en la sub-cadena actual.
							posSubcadAProbar += ciclos[posSubcadActual] - posSubcadActual;  // Salto en la sub-cadena a probar tantas posiciones como ocurrencias ininterrumpidas (repeticiones + 1) del caracter actual (a partir de la posición actual en la sub-cadena actual) hay en la sub-cadena actual.
							posSubcadActual = ciclos[posSubcadActual];  // Salto en la sub-cadena actual al siguiente caracter distinto.
						}
					}
				} else {  // El caracter actual de la sub-cadena a probar sí es el último de la sub-cadena buscada.
					// Sigo buscando porque puede ser que la sub-cadena actual esté compuesta de repeticiones completas de la sub-cadena a probar.
					diLaVueltaEnCadenaAProbar = true;
					posSubcadAProbar = inicioSubcadAProbar;
					posSubcadActual++;
				}
			} else {  // El caracter actual de la sub-cadena actual sí es el último de la sub-cadena buscada.
				diLaVueltaEnCadenaActual = true;
				posSubcadActual = inicioSubcadActual;
				if (posSubcadAProbar < ciclos[posSubcadAProbar]) {  // Si el caracter actual de la sub-cadena a probar no es el último de la sub-cadena buscada.
					// Sigo buscando porque la sub-cadena actual es solo el último caracter de la sub-cadena que aún no se "lyndonizó".
					posSubcadAProbar++;
				} else {  // El caracter actual de la sub-cadena a probar sí es el último de la sub-cadena buscada.
					// Ya no hace falta buscar más, al final de esta iteración sale del ciclo. Tengo que actualizar las posiciones para el caso de que la sub-cadena actual fuera solo el último caracter de la sub-cadena que aún no se "lyndonizó".
					diLaVueltaEnCadenaAProbar = true;
					posSubcadAProbar = inicioSubcadAProbar;
				}
			}
			if (bloque[posSubcadActual] != bloque[posSubcadAProbar]) {
				todaviaFalta = false;
			} else {
				if (diLaVueltaEnCadenaActual && diLaVueltaEnCadenaAProbar) {
					todaviaFalta = false;
				}
			}
		} while (todaviaFalta);
		if (bloque[posSubcadActual] != bloque[posSubcadAProbar]) {  // Si los caracteres de ambas sub-cadenas no son iguales.
			if (bloque[posSubcadActual] < bloque[posSubcadAProbar]) {  // Si el caracter de la sub-cadena actual es menor que el caracter de la sub-cadena que estoy probando.
				return false;  // No hay otra sub-cadena menor empezando en la posición "inicioSubcadAProbar".
			} else {
				return true;  // Si hay otra sub-cadena menor empezando en la posición "inicioSubcadAProbar".
			}
		} else {
			if (posSubcadActual < posSubcadAProbar) {
				// La sub-cadena actual está compuesta de repeticiones completas de la sub-cadena a probar.
				return false;
			} else {
				// La sub-cadena a probar está compuesta de repeticiones completas de la sub-cadena actual (la sub-cadena actual es solo el último caracter de la sub-cadena que aún no se "lyndonizó").
				return true;
			}
		}
	}
}

// Actualiza los valores del vector de ciclos (solo para los últimos caracteres idénticos de la sub-cadena).
void cerrarCiclo(unsigned char bloque[], unsigned int ciclos[], const int posicionInicio, const int posicionFin) {
	unsigned char caracterAnterior = bloque[posicionFin];  // Almaceno el último caracter de la cadena.
	unsigned int posicionCaracterDistinto = posicionFin;  // Almaceno la posición del último caracter de la cadena.
	// Recorro la cadena de derecha a izquierda (un ciclo por cada caracter).
	for (int posicionActual = posicionFin; posicionActual >= posicionInicio; --posicionActual) {  // TODO (Iván): Posible mejora, empezar con "posicionActual = posicionFin - 1".
		if (bloque[posicionActual] != caracterAnterior) {  // Si el caracter de esta posición es distinto al anterior.
			caracterAnterior = bloque[posicionActual];  // Almaceno el nuevo caracter.
			posicionCaracterDistinto = posicionActual + 1;  // Guardo la posición donde he visto el caracter anterior por última vez en la cadena.
		}
		if (ciclos[posicionActual] == posicionCaracterDistinto) {  // Si entro en un ciclo ya establecido.
			break;  // Estoy en un ciclo ya establecido, así que no necesito seguir marcando saltos.
		}
		ciclos[posicionActual] = posicionCaracterDistinto;  // Almaceno en la posición actual del vector de ciclos, la posición de la primera ocurrencia de un caracter distinto al actual en la cadena (comparando desde la posición actual).
	}
	ciclos[posicionFin] = posicionInicio;  // El ciclo se cierra haciendo apuntar la última posición del vector de ciclos a la posición de la cadena donde comienza la Lyndon word.
	return;
}

int compararSubcadenas(const unsigned int *pInicioSubcad1, const unsigned int *pInicioSubcad2) {
	unsigned int inicioSubcad1 = *pInicioSubcad1;
	unsigned int inicioSubcad2 = *pInicioSubcad2;

	if (bloque[inicioSubcad1] != bloque[inicioSubcad2]) {  // Si los primeros caracteres de ambas sub-cadenas no son iguales.
		if (bloque[inicioSubcad1] < bloque[inicioSubcad2]) {  // Si el primer caracter de la sub-cadena actual es menor que el primer caracter de la sub-cadena que estoy probando.
			return -1;  // No hay otra sub-cadena menor empezando en la posición "inicioSubcadAProbar".
		} else {
			return 1;  // Sí hay otra sub-cadena menor empezando en la posición "inicioSubcadAProbar".
		}
	} else {  //  Los primeros caracteres de ambas sub-cadenas son iguales.
		unsigned int posSubcadActual = inicioSubcad1;  // Hago una copia para poder ir recoriendo la sub-cadena.
		unsigned int posSubcadAProbar = inicioSubcad2;  // Hago una copia para poder ir recoriendo la sub-cadena.
		bool todaviaFalta = true;
		bool diUnaVueltaEnCadenaAProbar = false, diUnaVueltaEnCadenaActual = false;
		bool diDosVueltasEnCadenaAProbar = false, diDosVueltasEnCadenaActual = false;
		do {
			if (posSubcadActual < ciclos[posSubcadActual]) {  // Si el caracter actual de la sub-cadena actual no es el último de la sub-cadena buscada.
				if (posSubcadAProbar < ciclos[posSubcadAProbar]) {  // Si el caracter actual de la sub-cadena a probar no es el último de la sub-cadena buscada.
					unsigned int cantOcurrSubcadActual = ciclos[posSubcadActual] - posSubcadActual;  // Cantidad de ocurrencias ininterrumpidas (repeticiones + 1) del caracter actual en la sub-cadena actual a partir de la posición actual en la subcadena actual.
					unsigned int cantOcurrSubcadAProbar = ciclos[posSubcadAProbar] - posSubcadAProbar;  // Cantidad de ocurrencias ininterrumpidas (repeticiones + 1) del caracter actual en la sub-cadena a probar a partir de la posición actual en la subcadena a probar.
					if (cantOcurrSubcadActual == cantOcurrSubcadAProbar) {  // Si la cantidad de ocurrencias ininterrumpidas (repeticiones + 1) del caracter actual (a partir de las posiciones actuales respectivas) es igual en ambas sub-cadenas.
						posSubcadActual = ciclos[posSubcadActual];  // Salto en la sub-cadena actual al siguiente caracter distinto.
						posSubcadAProbar = ciclos[posSubcadAProbar];  // Salto en la sub-cadena a probar al siguiente caracter distinto.
					} else {  // La cantidad de ocurrencias ininterrumpidas (repeticiones + 1) del caracter actual (a partir de las posiciones actuales respectivas) no es igual en ambas sub-cadenas.
						if (cantOcurrSubcadActual > cantOcurrSubcadAProbar) {  // Si la cantidad de ocurrencias ininterrumpidas (repeticiones + 1) del caracter actual (a partir de las posiciones actuales respectivas) es mayor en la sub-cadena actual.
							// Salto en ambas sub-cadenas tantas posiciones como ocurrencias ininterrumpidas (repeticiones + 1) del caracter actual (a partir de la posición actual en la sub-cadena a probar) hay en la sub-cadena a probar.
							posSubcadActual += ciclos[posSubcadAProbar] - posSubcadAProbar;  // Salto en la sub-cadena actual tantas posiciones como ocurrencias ininterrumpidas (repeticiones + 1) del caracter actual (a partir de la posición actual en la sub-cadena a probar) hay en la sub-cadena a probar.
							posSubcadAProbar = ciclos[posSubcadAProbar];  // Salto en la sub-cadena a probar al siguiente caracter distinto.
						} else {  // La cantidad de ocurrencias ininterrumpidas (repeticiones + 1) del caracter actual (a partir de las posiciones actuales respectivas) es menor en la sub-cadena actual.
							// Salto en ambas sub-cadenas tantas posiciones como ocurrencias ininterrumpidas (repeticiones + 1) del caracter actual (a partir de la posición actual en la sub-cadena actual) hay en la sub-cadena actual.
							posSubcadAProbar += ciclos[posSubcadActual] - posSubcadActual;  // Salto en la sub-cadena a probar tantas posiciones como ocurrencias ininterrumpidas (repeticiones + 1) del caracter actual (a partir de la posición actual en la sub-cadena actual) hay en la sub-cadena actual.
							posSubcadActual = ciclos[posSubcadActual];  // Salto en la sub-cadena actual al siguiente caracter distinto.
						}
					}
				} else {  // El caracter actual de la sub-cadena a probar sí es el último de la sub-cadena buscada.
					// Sigo buscando porque puede ser que la sub-cadena actual esté compuesta de repeticiones completas de la sub-cadena a probar.
					if (diUnaVueltaEnCadenaAProbar == false) {
						diUnaVueltaEnCadenaAProbar = true;
					} else {
						diDosVueltasEnCadenaAProbar = true;
					}
					posSubcadAProbar = ciclos[posSubcadAProbar];
					posSubcadActual++;
				}
			} else {  // El caracter actual de la sub-cadena actual sí es el último de la sub-cadena buscada.
				if (diUnaVueltaEnCadenaActual == false) {
					diUnaVueltaEnCadenaActual = true;
				} else {
					diDosVueltasEnCadenaActual = true;
				}
				posSubcadActual = ciclos[posSubcadActual];
				if (posSubcadAProbar < ciclos[posSubcadAProbar]) {  // Si el caracter actual de la sub-cadena a probar no es el último de la sub-cadena buscada.
					// Sigo buscando porque la sub-cadena actual es solo el último caracter de la sub-cadena que aún no se "lyndonizó".
					posSubcadAProbar++;
				} else {  // El caracter actual de la sub-cadena a probar sí es el último de la sub-cadena buscada.
					// Ya no hace falta buscar más, al final de esta iteración sale del ciclo. Tengo que actualizar las posiciones para el caso de que la sub-cadena actual fuera solo el último caracter de la sub-cadena que aún no se "lyndonizó".
					if (diUnaVueltaEnCadenaAProbar == false) {
						diUnaVueltaEnCadenaAProbar = true;
					} else {
						diDosVueltasEnCadenaAProbar = true;
					}
					posSubcadAProbar = ciclos[posSubcadAProbar];
				}
			}
			if (bloque[posSubcadActual] != bloque[posSubcadAProbar]) {
				todaviaFalta = false;
			} else {
				if (diDosVueltasEnCadenaActual && diDosVueltasEnCadenaAProbar) {
					todaviaFalta = false;
				}
			}
		} while (todaviaFalta);
		if (bloque[posSubcadActual] != bloque[posSubcadAProbar]) {  // Si los caracteres de ambas sub-cadenas no son iguales.
			if (bloque[posSubcadActual] < bloque[posSubcadAProbar]) {  // Si el caracter de la sub-cadena actual es menor que el caracter de la sub-cadena que estoy probando.
				return -1;  // No hay otra sub-cadena menor empezando en la posición "inicioSubcadAProbar".
			} else {
				return 1;  // Si hay otra sub-cadena menor empezando en la posición "inicioSubcadAProbar".
			}
		} else {
			return 0;  // Si las dos cadenas son iguales.
		}
	}
}

int comparar(const unsigned int *pInicio, const unsigned int *pFin) {
	unsigned int inicio = *pInicio;
	unsigned int fin = *pFin;
	unsigned short int contadorInicio = 1;
	unsigned short int contadorFin = 1;
	if (bloque[inicio] != bloque[fin]) {
		return bloque[inicio] < bloque[fin] ? -1 : 1;
	}
	while (true) {
		if (inicio < ciclos[inicio]) {
			if (fin < ciclos[fin]) {
				if ((ciclos[inicio] - inicio) < (ciclos[fin] - fin)) {
					fin += ciclos[inicio] - inicio;
					inicio = ciclos[inicio];
				} else {
					if ((ciclos[inicio] - inicio) > (ciclos[fin] - fin)) {
						inicio += ciclos[fin] - fin;
						fin = ciclos[fin];
					} else {
						inicio = ciclos[inicio];
						fin = ciclos[fin];
					}
				}
			} else {
				if (contadorFin != 0) {
					contadorFin--;
				}
				fin = ciclos[fin];
				inicio++;
			}
		} else {
			if (fin < ciclos[fin]) {
				fin++;
			} else {
				if (contadorFin != 0) {
					contadorFin--;
				}
				fin = ciclos[fin];
			}
			inicio = ciclos[inicio];
			if (contadorInicio != 0) {
				contadorInicio--;
			}
		}
		if (bloque[inicio] != bloque[fin]) {
			break;
		}
		if ((contadorInicio + contadorFin) == 0) {
			break;
		}
	}
	if (bloque[inicio] != bloque[fin]) {
		return bloque[inicio] < bloque[fin] ? -1 : 1;
	}
	return 0;
}
